package com.zhongge.binarytreeOJ;


import com.zhongge.binarytreeOJ.question.MyBinTree;

import java.util.*;

/**
 * @ClassName MyBinaryTree
 * @Description TODO 自定义二叉树
 * @Author zhongge
 * @Date 2025/9/1 16:06
 * @Version 1.0
 */

public class MyBinaryTree {

   public static class TreeNode{
        public int val;
        public TreeNode left;

       public TreeNode(int val) {
           this.val = val;
       }

       public TreeNode right;

    }

    /**
     * 递归前序遍历
     * @param root 根节点
     */
    public void preOrder(TreeNode root) {
       //递归出口
        if (root == null) {
            return;//结束递归
        }
        //剪枝：无
        //递归核心代码
        System.out.print(root.val + " ");
        //递归入口
        preOrder(root.left);
        preOrder(root.right);
        //递归的归过程
        return;//不写他自动结束大括号的时候结束
    }

    /**
     * 递归中序遍历
     * @param root 根节点
     */
    public void inOrder(TreeNode root) {
        //递归出口
        if (root == null) {
            return;//结束递归
        }
        //剪枝：无

        //递归入口
        inOrder(root.left);
        //递归核心代码
        System.out.print(root.val + " ");

        inOrder(root.right);
        //递归的归过程
        return;//不写他自动结束大括号的时候结束
    }
    public void postOrder(TreeNode root) {
        //递归出口
        if (root == null) {
            return;//结束递归
        }
        //剪枝：无

        //递归入口
        postOrder(root.left);
        postOrder(root.right);
        //递归核心代码
        System.out.print(root.val + " ");
        //递归的归过程
        return;//不写他自动结束大括号的时候结束
    }

    //手动搭建一个二叉树
    public TreeNode createBinaryTree() {
        TreeNode a = new TreeNode(10);
        TreeNode b = new TreeNode(34);
        TreeNode c = new TreeNode(23);
        TreeNode d = new TreeNode(56);
        TreeNode e = new TreeNode(14);
        TreeNode f = new TreeNode(78);
        TreeNode g = new TreeNode(98);
        a.left = b;
        b.left = d;
        b.right = e;
        a.right = c;
        c.left = f;
        c.right = g;
        return a;
    }

    /**
     * 子问题求节点个数
     * @param root 根节点
     * @return 节点个数
     */
    public int nodeSize(TreeNode root){
        //递归出口
        if (root == null) {
            return 0;
        }
        //递归剪枝
        if (root.left == null && root.right == null) {
            return 1;
        }
        //递归核心:递归的递 + 递归的归 （虽然是同一个代码，但是执行时机不同，不可以说是同一个）
        return nodeSize(root.left) + nodeSize(root.right) +1;
    }

    public static int nodeSize;
    /**
     * 遍历思想求节点个数
     * @param root 根节点
     * @return 节点个数
     */
    public void nodeSizeOfOrder(TreeNode root){
        //递归出口
        if (root == null) {
            return;
        }

        //递归剪枝:无

        //递归核心：先处理根(当前节点)
        nodeSize++;

        //递归入口（递归的递）
        nodeSizeOfOrder(root.left);
        nodeSizeOfOrder(root.right);

        //递归的归:void
        //return;//可以不写
    }

    //二叉树的非递归实现遍历

   /**
     * 非递归实现前序遍历
     * @param root 根节点
     */
    public void preOrderNoRec(TreeNode root) {
        //使用栈记住来时路
        Deque<TreeNode> stack = new LinkedList<>();
        //从根节点开始扫描
        TreeNode cur = root;

        //记住上一次的出栈的节点
        TreeNode preNode = root;

        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {//去
                System.out.print(cur.val + " "); //====>根
                //去的时候记住来时路
                stack.push(cur);
                cur = cur.left;  // =========>左
            }else {
                //回去的时候 注意需要向右遍历
                //瞄一眼：看有没有右孩子
                TreeNode peek = stack.peek();
                if (peek.right != null && preNode != peek.right) {
                    //如果有右孩子:向右走
                    cur = peek.right; //=====> 右
                }else {
                    //出栈
                    preNode = stack.pop();
                }
            }
        }
        System.out.println();
    }
   /* *//**
     * 非递归实现中序遍历
     * @param root 根节点
     *//*
    public void inOrderNoRec(TreeNode root) {
        //使用栈记住来时路
        Deque<TreeNode> stack = new LinkedList<>();
        //从根节点开始扫描
        TreeNode cur = root;

        //记住上一次的出栈的节点
        TreeNode preNode = root;

        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {//去
                //去的时候记住来时路
                stack.push(cur);
                cur = cur.left;  // =========>左
            }else {
                //回去的时候 注意需要向右遍历
                //瞄一眼：看有没有右孩子
                TreeNode peek = stack.peek();

                if (peek.right != null && preNode != peek.right) {
                    //如果有右孩子:向右走
                    //没有右子树 或者 [有右子树右子树没有访问过的时候]
                    System.out.print(peek.val + " "); //====>根
                    cur = peek.right; //=====> 右
                }else {
                    //走到这说明：peek.right != null//右子树为空
                    //以及 preNOde == peek.right //右子树已经访问过
                    if (preNode != peek.right) {//右子树访问过已在上面做过了
                        //[没有右子树或者 右子树已经访问过]
                        System.out.print(peek.val + " "); //====>根
                    }

                    //出栈
                    preNode = stack.pop();
                }
            }
        }
        System.out.println();
    }*/

    /**
     * 非递归实现中序遍历
     * @param root 根节点
     */
    public void inOrderNoRec(TreeNode root) {
        //使用栈记住来时路
        Deque<TreeNode> stack = new LinkedList<>();
        //从根节点开始扫描
        TreeNode cur = root;

        //记住上一次的出栈的节点
        TreeNode preNode = null;

        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {//去
                //去的时候记住来时路
                stack.push(cur);
                cur = cur.left;  // =========>左
            }else {
                //回去的时候 注意需要向右遍历
                //瞄一眼：看有没有右孩子
                TreeNode peek = stack.peek();
                if (peek.right != null && preNode != peek.right) {
                    //有右节点且右节点没有处理过
                    System.out.print(peek.val + " ");
                    cur = peek.right;
                } else {
                    //peek.right == null  preNode =null 没有右节点

                    //preNode == peek.right 右节点处理过

                    //此处的打印只是处理没有右节点且右节点没有处理过
                    //这个只在第一次成立preNode == null 因为最初的preNode初值是null
                    if (preNode == null || preNode != peek.right) {
                        System.out.print(peek.val + " ");
                    }
                    preNode = stack.poll();
                }
            }
        }
        System.out.println();
    }
    /**
     * 非递归实现后序遍历
     * @param root 根节点
     */
    public void postOrderNoRec(TreeNode root) {
        //使用栈记住来时路
        Deque<TreeNode> stack = new LinkedList<>();
        //从根节点开始扫描
        TreeNode cur = root;

        //记住上一次的出栈的节点
        TreeNode preNode = root;

        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {//去
                //去的时候记住来时路
                stack.push(cur);
                cur = cur.left;  // =========>左
            }else {
                //回去的时候 注意需要向右遍历
                //瞄一眼：看有没有右孩子
                TreeNode peek = stack.peek();
                if (peek.right != null && preNode != peek.right) {
                    //如果有右孩子:向右走
                    cur = peek.right; //=====> 右
                }else {
                    //出栈
                    preNode = stack.pop();
                    System.out.print(peek.val + " "); //====>根
                }
            }
        }
        System.out.println();
    }

   /* *//**
     * 非递归实现前序遍历
     * @param root 根节点
     *//*
    public void preOrderNoRec(TreeNode root) {
        //使用栈记住来时路
        Deque<TreeNode> stack = new LinkedList<>();
        //从根节点开始扫描
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {//去
                System.out.print(cur.val + " "); //====>根
                //去的时候记住来时路
                stack.push(cur);
                cur = cur.left;  // =========>左
            }else {
                //回去的时候 注意需要向右遍历
                //瞄一眼：看有没有右孩子
                TreeNode pop = stack.pop();
                if (pop.right != null) {
                    //如果有右孩子:向右走
                    cur = pop.right; //=====> 右
                }
            }
        }
        System.out.println();
    }
    *//**
     * 非递归实现中序遍历
     * @param root 根节点
     *//*
    public void inOrderNoRec(TreeNode root) {
        //使用栈记住来时路
        Deque<TreeNode> stack = new LinkedList<>();
        //从根节点开始扫描
        TreeNode cur = root;


        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {//去
                //去的时候记住来时路
                stack.push(cur);
                cur = cur.left;  // =========>左
            }else {
                //回去的时候 注意需要向右遍历
                //瞄一眼：看有没有右孩子
                TreeNode pop = stack.pop();
                System.out.print(pop.val + " "); //====>根
                if (pop.right != null) {
                    //如果有右孩子:向右走
                    cur = pop.right; //=====> 右
                }
            }
        }
        System.out.println();
    }


    *//**
     * 非递归实现后序遍历
     * @param root 根节点
     *//*
    public void postOrderNoRec(TreeNode root) {
        //使用栈记住来时路
        Deque<TreeNode> stack = new LinkedList<>();
        //从根节点开始扫描
        TreeNode cur = root;

        //记住上一次的出栈的节点
        TreeNode preNode = root;

        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {//去
                //去的时候记住来时路
                stack.push(cur);
                cur = cur.left;  // =========>左
            }else {
                //回去的时候 注意需要向右遍历
                //瞄一眼：看有没有右孩子
                TreeNode peek = stack.peek();
                if (peek.right != null && preNode != peek.right) {
                    //如果有右孩子:向右走
                    cur = peek.right; //=====> 右
                }else {
                    //出栈
                    preNode = stack.pop();
                    System.out.print(preNode.val + " "); //====>根
                }
            }
        }
        System.out.println();
    }*/


    //力扣二叉树中序遍历==》非递归
    /**
     方法一：直接出栈，无需走遍所有的节点
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        //判断安全
        if (root == null) {
            return list;
        }

        //使用栈来存储来时路
        Deque<TreeNode> stack = new LinkedList<>();

        //使用一个遍历指针
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                //入栈
                stack.push(cur);
                //向左
                cur = cur.left;
            } else {
                TreeNode pop = stack.pop();//直接出栈
                //每出一次说明左子树完了 直接存值
                list.add(pop.val);

                if (pop.right != null) {
                    cur = pop.right;//根并没有在栈中停留，所以你右子树做完后 回不到根
                }
            }
        }
        return list;
    }
    /**
     方法二：走遍所有的节点
     */
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        //判断安全
        if (root == null) {
            return list;
        }

        //使用栈来存储来时路
        Deque<TreeNode> stack = new LinkedList<>();

        //使用一个遍历指针
        TreeNode cur = root;

        //记录上一个出栈的节点
        TreeNode preNode = root;

        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                //入栈
                stack.push(cur);
                //向左
                cur = cur.left;
            } else {
               TreeNode peek = stack.peek();

               if (peek.right != null && peek.right != preNode) {
                   //有右孩子 且 右孩子没处理过
                   list.add(peek.val);
                   cur = peek.right;
               } else {
                   //peek.right == null
                   //peek.right == preNode//右孩子已经处理过了
                   if(peek.right != preNode) {//没右孩子 且 右孩子没处理过
                       list.add(peek.val);
                   }
                   preNode = stack.poll();
               }
            }
        }
        return list;
    }

    /**
     * 非递归实现后序遍历
     * @param root 根节点
     * @return 集合
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        //判断安全
        if (root == null) {
            return list;
        }

        //使用栈来存储来时路
        Deque<TreeNode> stack = new LinkedList<>();

        //使用一个遍历指针
        TreeNode cur = root;

        //记录上一个出栈的节点
        TreeNode preNode = root;

        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                //入栈
                stack.push(cur);
                //向左
                cur = cur.left;
            } else {
                TreeNode peek = stack.peek();

                if (peek.right != null && peek.right != preNode) {

                    cur = peek.right;
                } else {
                    //peek.right == null
                    //peek.right == preNode//右孩子已经处理过了

                    list.add(peek.val);//只在右孩子处理完毕后处理即可

                    preNode = stack.poll();
                }
            }
        }
        return list;
    }
    /**
     * 非递归实现前序遍历
     * @param root 根节点
     * @return 集合
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        //判断安全
        if (root == null) {
            return list;
        }

        //使用栈来存储来时路
        Deque<TreeNode> stack = new LinkedList<>();

        //使用一个遍历指针
        TreeNode cur = root;

        //记录上一个出栈的节点
        TreeNode preNode = root;

        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                list.add(cur.val);//只在左孩子处理之前处理即可
                //入栈
                stack.push(cur);
                //向左
                cur = cur.left;
            } else {
                TreeNode peek = stack.peek();

                if (peek.right != null && peek.right != preNode) {

                    cur = peek.right;
                } else {
                    //peek.right == null
                    //peek.right == preNode//右孩子已经处理过了

                    preNode = stack.poll();
                }
            }
        }
        return list;
    }

    /**
     * 根据前序和中序构建 二叉树
     * @param preorder 前序
     * @param inorder 中序
     * @return 根节点
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //递归出口
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }
        //递归剪枝：没有
        //递归代码
        //1.前序==》先找到根
        int rootIndex = preorder[0];
        //创建根节点
        TreeNode root = new TreeNode(rootIndex);
        //2.有根找到根在中序中的位置，从而确定子树
        for (int i = 0; i < inorder.length; i++) {
            if (rootIndex == inorder[i]) {
                //确定左子树和右子树的个数
                //切割中序 从而得出中序左子树 和 右子树的个数
                int[] inLeft = Arrays.copyOfRange(inorder, 0, i);//下标顾前不顾后[0, i)==> [0, i - 1]
                int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);//下标顾前不顾后[i + 1, inorder.length)==>[i+1, inorder.length-1]

                //那么根据中序中的左右子树个数将前序左右子树也要进行相应的切割 从而进行左右子树的树的构建
                int[] preLeft = Arrays.copyOfRange(preorder, 1, inLeft.length + 1);//从1开始向后数中序子树的个数(因为前序和中序个数一定是相同的)
                //[1, inLeft.length + 1)==>[1, inLeft.length]==》下标到达(1 + inLeft.length)
                //那么下一次就从(1 + inLeft.length)开始  （这一步最好的办法就是画图理解）
                int[] preRight = Arrays.copyOfRange(preorder, inLeft.length + 1, preorder.length);//从左子树向后遍历后的下标开始 到 前序的最后一个下标

                //递归构建左右子树
                root.left = buildTree(preLeft, inLeft);//前序的左子树和中序的左子树==》构建左子树的树
                root.right = buildTree(preRight, inRight);//前序的右子树和中序的右子树==》构建左子树的树

                break;//找到就没必要往后找了（一定是找得到的）
            }
        }
        //递归的归
        return root;
    }

}
